Thuật toán có thể viết như sau:

Inputs: n: giá trị để kiểm tra tính nguyên tố; k: tham số tham gia vào quá trình kiểm traOutput: hợp số nếu n là hợp số, nếu không nguyên tố xác suấtrepeat k times:lấy a ngẫu nhiên trong [1, n − 1]if an − 1 mod n ≠ 1 then return compositereturn probably prime

Khi dùng thuật toán tính nhanh luỹ thừa theo mođun, thời gian thi hành của thuật toán là O(k × log3n), ở đó k là số lần kiểm tra với mỗi số a ngãu nhiên, và n là giá trị ta muốn kiểm tra.